COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a88.tex[106,phy] \today\hfill}

\bigskip
\line{{\bf Time Bombs.} [To follow section on testing.]\hfill}

Alan Turing, who designed the first programmable computer to break codes
during World War~II, rode a bicycle which had a defective link in its chain
and a defective tooth on its sprocket. After a certain number of turns of
the pedal crank, the defective link would meet the defective tooth and
the chain would fall off. Turing would jump off the bicycle, remount the
chain, and continue on his way.

Many computer programs are like Turing's bicycle. Their logical flaws
are harmless until several of them come together. Such a program may rattle
on for years, like Faulkner's mule that works faithfully for its
master for a dozen years in return for the chance to kick him once
[RWF: Find exact quotation]. I~call such programs {\it time bombs\/}.
Their flaws are dangerous because they appear when the program has become
accepted as trustworthy, and often when the designers who understood
the program well enough to repair it have vanished or have forgotten
how it worked.

Testing a program on problems with known answers is seldom sufficient to
discover time bombs. Turing's bicycle would
usually work for more than one complete
turn of the chain and of the sprocket.

{\narrower\noindent\smallskip
{\it Testing can show the presence of errors in a program; it can not
show their absence.}
\smallskip}

The Apollo manned lunar lander carried a time bomb in its on-board
computer. That computer shared its time among several tasks. If a task
was not finished in its allotted time, it was abandoned, to be started
from the beginning when its next turn arose. Its radar altimeter had
been tested, and seemed to work. Only when the lander came close to
the surface of the moon did the increasing
amount of data require more than
the allotted time to process. The astronauts got no altitude information
until an improvised solution sent them altitude calculations, a~few
seconds late, from an earth-bound computer.

It is the responsibility of a serious computer programmer to do whatever
is humanly possible to avoid building time bombs. This is best done
by making explicit, and examining critically, every assumption on
which the correct operation of a program depends. The careful working
out of the consequences of assumptions is the domain of mathematics,
which provides protections against sloppy reasoning. If I~say in
ordinary language ``I~know that $A$ isn't any bigger than~$B$, and
$C$~is at least as large as~$B$, so $C$~must be bigger than~$A$,''
I~may falsely believe that I~can safely divide something by $C-A$.
If I~say ``$A≤B≤C$ implies $A<C$,'' I~am likely to see that it
doesn't follow. I~then use the mathematician's way of finding an
exception, or {\it counterexample\/}: I~assume the hypothesis true
and the conclusion false, and see what I~can deduce. In the current
example, that means assuming that $A≤B≤C$ and $C≤A$, from which I~can
deduce $A=B=C$; I~then examine whether the program can ever make the
three varianbles equal, and what will happen next if it does.

{\rmn
{\narrower\smallskip\noindent
{\bf Example.}

A program reads from a data file a list of license numbers of stolen
cars and stores them in an array of size~100, first checking that the
number~$N$ of license numbers is no more than~100. Later it searches
the array for the license number of an abandoned car to see if it has
been reported stolen. As a sentinel to end the search, the program puts
the license number of the abandoned car into the $(N+1)↑{\rm st}$
position in the array. The relevant fragment of the program is:

\smallskip
\halign{\qquad\qquad{\tt #}\hfil\cr
STOLEN[N+1]:=ABAND;\cr
I:=1;\cr
WHILE ABAND <> STOLEN[I] DO I:=I+1;\cr
IF I<=N THEN WRITE('STOLEN CAR')...\cr}

\smallskip\noindent
The hidden assumption is that $N+1$ is a valid index for the array
{\tt STOLEN}, that $N+1≤100$. From the hypothesis $N≤100$, and the
negated conclusion $N+1>100$, we find the time bomb $N=100$.
When $N=100$, the program may stop with an unanticipated error
condition (``subscript out of range''). Worse yet, if it does not check
index ranges it may store {\tt ABAND} in the computer's memory where
some other variable, or constant, or program step, should be stored.
The consequences could be chaotic.

Notice that the bomb goes off only if the number of stolen cars is
exactly 100, and if the abandoned car is not stolen,
and even then there might be no detectable effect.
\smallskip}
}


\bigskip
\line{\copyright 1985 Robert W. Floyd\hfill}
\line{First draft (not published) September 19, 1985;\hfil}
%revised: Date; subsequently revised.\hfill}

\bye